﻿#ifndef SWEEP_CIRCLE_VORONOI
#define SWEEP_CIRCLE_VORONOI

struct Edge;
struct Event;
struct Ellipse;
struct EllipseArc;
struct ActiveEdge;
struct VanishEvent;



//struct __align__(8) Edge{
//	int vert1,vert2;
//	//Edge(){}
//	//Edge(int _vert1,int _vert2):vert1(_vert1),vert2(_vert2){}
//	__device__ void initial(int _vert1,int _vert2){
//		vert1 = _vert1;
//		vert2 = _vert2;
//	}
//	
//};
//

struct Ellipse
{
	float2 majorFocus;
	float2 minorFocus;
	float rotateAngle;
	float c;
	__device__ void initial(float2 _majorFocus,float2 _minorFocus){
		majorFocus = _majorFocus;
		minorFocus = _minorFocus;
		rotateAngle = atan2f(minorFocus.y - majorFocus.y,minorFocus.x - majorFocus.x);
		c=sqrtf((majorFocus.x-minorFocus.x)*(majorFocus.x-minorFocus.x)+
			(majorFocus.y-minorFocus.y)*(majorFocus.y-minorFocus.y))/2;

	}
	/*__device__ Ellipse(float2 _majorFocus,float2 _minorFocus):majorFocus (_majorFocus), minorFocus (_minorFocus ){
		float detaX = minorFocus.x - majorFocus.x;
		float detaY = minorFocus.y - majorFocus.y;
		rotateAngle = atan2f(detaY,detaX);
		c=sqrtf((majorFocus.x-minorFocus.x)*(majorFocus.x-minorFocus.x)+
			(majorFocus.y-minorFocus.y)*(majorFocus.y-minorFocus.y))/2;
	}*/
	__device__ float GetA(float d){
		return d / 2;
	}
	__device__ float GetC(){
		return c;
	}
	__device__ float GetE(float d){
		return GetC()/GetA(d);
	}
	__device__ float GetP(float d){
		float a = GetA(d);
		float c = GetC();
		return a * a / c - c;
	}
	__device__ float GetRotateAngle(){
		return rotateAngle;
	}
	__device__ float2 GetPointAtAngleParam(float d,float angle){
		float e = GetE(d);
		float p = GetE(d);
		if( !(p>WXN_EPSILON) ){
			//assert(p>WXN_EPSILON);
			cuPrintf("p>WXN_EPSILON ,error!\n");

		}
		float alpha = GetRotateAngle();
		float rou = e * p / ( 1 - e * cos(angle - alpha) );
		float2 pt;
		pt = make_float2(rou * cos(angle),rou * sin(angle));
		pt.x += majorFocus.x;
		pt.y += majorFocus.y;
		return pt;
	}
	__device__ static float2 GetIntersectionAngleParam(Ellipse& ellipse1,Ellipse& ellipse2,float d){
		float e1 = ellipse1.GetE(d);
		float e2 = ellipse2.GetE(d);
		float p1 = ellipse1.GetP(d);
		float p2 = ellipse2.GetP(d);
		float alpha1 = ellipse1.GetRotateAngle();
		float alpha2 = ellipse2.GetRotateAngle();
		float a = p2 * cos(alpha1) - p1 * cos(alpha2);
		float b = p2 * sin(alpha1) - p1 * sin(alpha2);
		float c = (e2 * p2 - e1 * p1) / (e1 * e2);
		float len = sqrtf(a*a+b*b);
		a /= len;
		b /= len;
		c /= len;
		float t = atan2(b,a);
		float t2;
		if( c >= 1 )
			t2 = 0;
		else if ( c <= -1)
			t2 = M_PI;
		else 
			t2 = acosf(c);
		return make_float2(t-t2,t+t2);
	}
};

struct EllipseArc : Ellipse
{
	
	bool outofdate;
	float tolerance;
	ActiveEdge* leftActiveEdge;
	ActiveEdge* rightActiveEdge;

	__device__ void initial(float2 _majorFocus,float2 _minorFocus,ActiveEdge* _leftActiveEdge,ActiveEdge* _rightActiveEdge){
		Ellipse::initial(_majorFocus,_minorFocus);
		leftActiveEdge=_leftActiveEdge;
		rightActiveEdge = _rightActiveEdge;
		outofdate = false;
	}

	__device__ void GetVanishEvent(float &keyDis,Event& evt,float2* d_vertexPool,float2* d_vertexPoolLength  );

	__device__ bool Zero(float d){
		float2 angles = GetAngles(d);
		return angles.y - angles.x < WXN_EPSILON;
	}
	__device__ float2 GetAngles(float d);


};

struct ActiveEdge{//not complete
	EllipseArc* leftArc;
	EllipseArc* rightArc;
	int fixedVertex;
	float2 direction;
	__device__ void initial(EllipseArc* _leftArc,EllipseArc* _rightArc,int _fixedVertex){
		leftArc = _leftArc;
		rightArc = _rightArc;
		fixedVertex = _fixedVertex;
		direction = GetDirection(_leftArc->minorFocus,_rightArc->minorFocus);
	}
	/*ActiveEdge(EllipseArc* _leftArc,EllipseArc* _rightArc,int _fixedVertex):leftArc(_leftArc),rightArc(_rightArc),fixedVertex(_fixedVertex){
		float2 p1 = _leftArc->minorFocus;
		float2 p2 = _rightArc->minorFocus;
		direction = GetDirection(p1,p2);
	}*/
	__device__ float2 GetCurrentPos(float d ){
		if( leftArc == NULL || rightArc == NULL ){
			cuPrintf("error in GetCurrentPos\n");
		}
		if( leftArc->GetP(d) < WXN_EPSILON && rightArc->GetP(d) < WXN_EPSILON ){
			return leftArc->majorFocus;
		}
		if(leftArc->GetP(d) < WXN_EPSILON){
			float angle = atan2f(leftArc->minorFocus.y - leftArc->majorFocus.y,leftArc->minorFocus.x - leftArc->majorFocus.x);
			return leftArc->GetPointAtAngleParam(d,angle);
		}
		if(rightArc->GetP(d) < WXN_EPSILON){
			float angle = atan2f(rightArc->minorFocus.y - rightArc->majorFocus.y,rightArc->minorFocus.x - rightArc->majorFocus.x);
		}
		float2 params = Ellipse::GetIntersectionAngleParam(*leftArc,*rightArc,d);
		float2 p1 = leftArc->GetPointAtAngleParam(d,params.x);
		float2 p2 = leftArc->GetPointAtAngleParam(d,params.y);
		if((p2.x-p1.x)*direction.x + (p2.y-p1.y)*direction.y>0){
			return p2;
		}else{
			return p1;
		}
	}
	float2 __device__ GetDirection(float2 p1 , float2 p2)
	{
		if( p1.x == p2.x && p1.y == p2.y ){
			cuPrintf("direction error!\n");
			return;
		}
		float x = p1.y - p2.y;
		float y = p2.x - p1.x;
		float len = sqrt(x*x+y*y);
		return make_float2(x/len,y/len);
	}
};

enum EventType {NewEllipse,EllipseVanish};

struct __align__(16) Event{
	float distance;
	int type;
	float2 site;
	EllipseArc* arc;
	ActiveEdge* leftActiveEdge;
	ActiveEdge* rightActiveEdge;
	__device__ bool operator<(const Event& other)const{
		return distance < other.distance;
	}
};
__device__ void EllipseArc::GetVanishEvent(float &keyDis,Event& evt,float2* d_vertexPool,float2* d_vertexPoolLength  ){
	evt.type = EllipseVanish;
	keyDis = FLT_MAX;
	evt.arc = this;
	if(leftActiveEdge==NULL || rightActiveEdge == NULL){
		return;
	}
	if(leftActiveEdge->fixedVertex == rightActiveEdge->fixedVertex){
		return;
	}
	if(fabsf(leftActiveEdge->direction.x * rightActiveEdge->direction.x+leftActiveEdge->direction.y * rightActiveEdge->direction.y)>1.0 - FLT_EPSILON){
		return;
	}
	float e1 = d_vertexPool[leftActiveEdge->fixedVertex].x - d_vertexPool[rightActiveEdge->fixedVertex].x;
	float e2 = d_vertexPool[leftActiveEdge->fixedVertex].y - d_vertexPool[rightActiveEdge->fixedVertex].y;
	float a = -leftActiveEdge->direction.x;
	float b = rightActiveEdge->direction.x;
	float c = -leftActiveEdge->direction.y;
	float d = rightActiveEdge->direction.y;
	float mod = a * d - b * c;
	float tLeft = d * e1 - b * e2;
	tLeft /= mod;
	float tRight = -c * e1 + a * e2;
	tRight /= mod;
	if(tLeft < -FLT_EPSILON || tRight < -FLT_EPSILON){
		return;
	}
	if(tLeft<0)
		tLeft = 0;
	if(tRight<0)
		tRight = 0;
	float2 circumcenter;
	circumcenter.x = d_vertexPool[leftActiveEdge->fixedVertex].x + tLeft * leftActiveEdge->direction.x;
	circumcenter.y = d_vertexPool[leftActiveEdge->fixedVertex].y + tLeft * leftActiveEdge->direction.y;
	float dis = sqrtf((circumcenter.x - minorFocus.x)*(circumcenter.x - minorFocus.x)+(circumcenter.y - minorFocus.y)*(circumcenter.y-minorFocus.y));
	dis += sqrtf((circumcenter.x - majorFocus.x) * (circumcenter.x - majorFocus.x)+(circumcenter.y-majorFocus.y)*(circumcenter.y - majorFocus.y));
	keyDis = dis;
	evt.leftActiveEdge = leftActiveEdge;
	evt.rightActiveEdge = rightActiveEdge;
	evt.site = circumcenter;
	return;
}

__device__ float2  EllipseArc::GetAngles(float d)
{
	if(leftActiveEdge==NULL){
		return make_float2(0,2*M_PI);
	}
	if(rightActiveEdge == NULL ){
		cuPrintf("error in GetAngles");
		return;
	}
	if(GetP(d)<FLT_EPSILON){
		if(fabsf(minorFocus.y - majorFocus.y) + fabsf(minorFocus.x - majorFocus.x)<WXN_EPSILON){
			cuPrintf("error in get angles\n");
			return;
		}else{
			return make_float2(GetRotateAngle(),GetRotateAngle());
		}
	}
	float2 leftP = leftActiveEdge->GetCurrentPos(d);
	float2 rightP = rightActiveEdge->GetCurrentPos(d);
	if( fabsf(rightP.y - majorFocus.y)+fabsf(rightP.x - majorFocus.x)< WXN_EPSILON ){
		cuPrintf("error in get angles\n");
		return;
	}
	float angle1 = atan2f(rightP.y - majorFocus.y ,rightP.x - majorFocus.x);
	if( fabsf(leftP.y - majorFocus.y) + fabsf(leftP.x - majorFocus.x ) < WXN_EPSILON ){
		cuPrintf("error in get angles\n");
	}
	float angle2 = atan2f(leftP.y - majorFocus.y,leftP.x - majorFocus.x );
	if( angle2 < angle1 - WXN_EPSILON ){
		angle2 += 2 * M_PI;
	}else if ( angle2 < angle1 + WXN_EPSILON && leftActiveEdge->leftArc == rightActiveEdge->rightArc ){
		angle2 += 2 * M_PI;
	}else if( angle2 - angle1 > 2 * M_PI - WXN_EPSILON){
		angle1 = angle2;
	}
	return make_float2(angle1,angle2);
}






struct __align__(8) ArcHeapEle{
	float angle;
	EllipseArc* arc;
	__device__ ArcHeapEle(float _angle,EllipseArc* _arc){
		angle = _angle;
		arc = _arc;
	}
	__device__ bool operator<(const ArcHeapEle& other) const{
		return angle < other.angle;
	}
};


float2* h_sites;
float2* d_sites;
int* h_sitesLength;
int* d_sitesLength;
int* h_vertexPoolLength;
float2* h_vertexPool;
int* d_vertexPoolLength;
float2* d_vertexPool;
int* h_edgePoolLength;
int2* h_edgePool;
int* d_edgePoolLength;
int2* d_edgePool;
EllipseArc* h_arcsPool;
int* h_arcsPoolLength;
EllipseArc* d_arcsPool;
int* d_arcsPoolLength;
ActiveEdge* d_activeEdgePool;
int* d_activeEdgePoolLength;


float radiusVaring;
float2* h_center;
float2* d_center;

float2 MinPoint;
float2 MaxPoint;

float distance;
float distanceGap;




Event* d_eventHeap;//allocate device memory in host,to pass point to device function
ArcHeapEle* d_arcHeap;


#endif

